package com.lagou;




/**
 * 给定一个链表，判断链表中是否有环。存在环返回 true ，否则返回 false，约束时间复杂度为 O(n)。
 */
public class Title2 {

    public static boolean isRing(Node head) {
        if (head == null) return false;

        //定义快慢指针
        Node slow = head; //慢指针
        Node fast = head.next; //快指针
        while (fast != null && fast.next != null){
            //有环
            if (slow == fast){
                return true;
            }
            fast = fast.next.next; //快指针步长为2
            slow = slow.next; //慢指针步长为1
        }
        return false;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1,"张飞");
        Node node2 = new Node(2,"关于");
        Node node3 = new Node(3,"赵云");
        Node node4 = new Node(4,"黄忠");
        Node node5 = new Node(5,"马超");
        System.out.println(isRing(node5));
    }

}
